Clover icon

compiler

  1. Project Clover database Mon Jan 2 2023 15:09:37 MST
  2. Package com.google.javascript.jscomp.graph

File Graph.java

 

Coverage histogram

../../../../../img/srcFileCovDistChart10.png
0% of files have more coverage

Code metrics

10
38
17
5
353
132
22
0.58
2.24
3.4
1.29

Classes

Class Line # Actions
Graph 57 28 16 0
1.0100%
Graph.AnnotationState 62 2 1 0
1.0100%
Graph.GraphAnnotationState 76 1 1 0
1.0100%
Graph.GraphEdge 289 0 0 0
-1.0 -
Graph.SimpleSubGraph 306 7 4 0
1.0100%
 

Contributing tests

This file is covered by 8905 tests. .

Source view

1    /*
2    * Copyright 2008 The Closure Compiler Authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10    * Unless required by applicable law or agreed to in writing, software
11    * distributed under the License is distributed on an "AS IS" BASIS,
12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13    * See the License for the specific language governing permissions and
14    * limitations under the License.
15    */
16   
17    package com.google.javascript.jscomp.graph;
18   
19    import com.google.common.base.Preconditions;
20    import com.google.common.collect.Lists;
21   
22    import java.util.ArrayList;
23    import java.util.Collection;
24    import java.util.Deque;
25    import java.util.Iterator;
26    import java.util.List;
27   
28    /**
29    * The base generic class for graph-like data structure and algorithms in
30    * the compiler.
31    * <p>
32    * Nodes and edges in the graph can store a piece of data that this graph is
33    * used to represent. For example, a variable interference graph might store a
34    * variable in the node. This piece of data can be accessed with
35    * {@link GraphNode#getValue} and {@link GraphEdge#getValue}.
36    * <p>
37    * Algorithms and analysis can annotate information on the nodes and edges
38    * using {@link GraphNode#getValue} and {@link GraphEdge#getValue}. For example,
39    * a graph coloring algorithm can store the color as an annotation. If multiple
40    * analyses are required, it is up to the user of the analysis to save the
41    * annotated solution between passes.
42    * <p>
43    * We implemented our own graph data structure (as opposed to using
44    * <code>com.google.common.graph</code>) for two reasons. First, aside from
45    * the node's label value, we would like to annotate information on the nodes
46    * and edges. Using a map to annotate would introduce too much overhead during
47    * fix point analysis. Also, <code>com.google.common.graph</code> does not
48    * support labeling of edges. Secondly, not using another external package would
49    * limit our dependencies.
50    * <p>
51    * TODO(user): All functionality for removing nodes and edges.
52    *
53    *
54    * @param <N> Value type that the graph node stores.
55    * @param <E> Value type that the graph edge stores.
56    */
 
57    public abstract class Graph<N, E> implements AdjacencyGraph<N, E> {
58    /**
59    * Pseudo typedef for a pair of annotations. Record of an object's
60    * annotation at some state.
61    */
 
62    private static final class AnnotationState {
63    private final Annotatable first;
64    private final Annotation second;
65   
 
66  4240 toggle public AnnotationState(Annotatable annotatable, Annotation annotation) {
67  4240 this.first = annotatable;
68  4240 this.second = annotation;
69    }
70    }
71   
72    /**
73    * Pseudo typedef for ArrayList<AnnotationState>. Record of a collection of
74    * objects' annotations at some state.
75    */
 
76    private static class GraphAnnotationState extends ArrayList<AnnotationState> {
77    private static final long serialVersionUID = 1L;
78   
 
79  640 toggle public GraphAnnotationState(int size) {
80  640 super(size);
81    }
82    }
83   
84    /**
85    * Used by {@link #pushNodeAnnotations()} and {@link #popNodeAnnotations()}.
86    */
87    private Deque<GraphAnnotationState> nodeAnnotationStack;
88   
89    /**
90    * Used by {@link #pushEdgeAnnotations()} and {@link #popEdgeAnnotations()}.
91    */
92    private Deque<GraphAnnotationState> edgeAnnotationStack;
93   
94    /**
95    * Connects two nodes in the graph with an edge.
96    *
97    * @param n1 First node.
98    * @param edge The edge.
99    * @param n2 Second node.
100    */
101    public abstract void connect(N n1, E edge, N n2);
102   
103    /**
104    * Disconnects two nodes in the graph by removing all edges between them.
105    *
106    * @param n1 First node.
107    * @param n2 Second node.
108    */
109    public abstract void disconnect(N n1, N n2);
110   
111    /**
112    * Connects two nodes in the graph with an edge if such edge does not already
113    * exists between the nodes.
114    *
115    * @param n1 First node.
116    * @param edge The edge.
117    * @param n2 Second node.
118    */
 
119  261848 toggle public final void connectIfNotFound(N n1, E edge, N n2) {
120  261848 if (!isConnected(n1, edge, n2)) {
121  261831 connect(n1, edge, n2);
122    }
123    }
124   
125    /**
126    * Gets a node from the graph given a value. New nodes are created if that
127    * value has not been assigned a graph node. Values equality are compared
128    * using <code>Object.equals</code>.
129    *
130    * @param value The node's value.
131    * @return The corresponding node in the graph.
132    */
133    public abstract GraphNode<N, E> createNode(N value);
134   
135    /** Gets an immutable list of all nodes. */
136    @Override
137    public abstract Collection<GraphNode<N, E>> getNodes();
138   
139    /** Gets an immutable list of all edges. */
140    public abstract List<GraphEdge<N, E>> getEdges();
141   
142    /**
143    * Gets the degree of a node.
144    *
145    * @param value The node's value.
146    * @return The degree of the node.
147    */
148    public abstract int getNodeDegree(N value);
149   
 
150  3058 toggle @Override
151    public int getWeight(N value) {
152  3058 return getNodeDegree(value);
153    }
154   
155    /**
156    * Gets the neighboring nodes.
157    *
158    * @param value The node's value.
159    * @return A list of neighboring nodes.
160    */
161    public abstract List<GraphNode<N, E>> getNeighborNodes(N value);
162   
163    public abstract Iterator<GraphNode<N, E>> getNeighborNodesIterator(N value);
164   
165    /**
166    * Retrieves an edge from the graph.
167    *
168    * @param n1 Node one.
169    * @param n2 Node two.
170    * @return The list of edges between those two values in the graph.
171    */
172    public abstract List<GraphEdge<N, E>> getEdges(N n1, N n2);
173   
174    /**
175    * Retrieves any edge from the graph.
176    *
177    * @param n1 Node one.
178    * @param n2 Node two.
179    * @return The first edges between those two values in the graph. null if
180    * there are none.
181    */
182    public abstract GraphEdge<N, E> getFirstEdge(N n1, N n2);
183   
184    /**
185    * Checks whether the node exists in the graph ({@link #createNode(Object)}
186    * has been called with that value).
187    *
188    * @param n Node.
189    * @return <code>true</code> if it exist.
190    */
 
191  5302 toggle public final boolean hasNode(N n) {
192  5302 return getNode(n) != null;
193    }
194   
195    /**
196    * Checks whether two nodes in the graph are connected.
197    *
198    * @param n1 Node 1.
199    * @param n2 Node 2.
200    * @return <code>true</code> if the two nodes are connected.
201    */
202    public abstract boolean isConnected(N n1, N n2);
203   
204    /**
205    * Checks whether two nodes in the graph are connected by the given
206    * edge type.
207    *
208    * @param n1 Node 1.
209    * @param e The edge type.
210    * @param n2 Node 2.
211    */
212    public abstract boolean isConnected(N n1, E e, N n2);
213   
214    /**
215    * Gets the node of the specified type, or throws an
216    * IllegalArgumentException.
217    */
 
218  2255260 toggle @SuppressWarnings("unchecked")
219    <T extends GraphNode<N, E>> T getNodeOrFail(N val) {
220  2255260 T node = (T) getNode(val);
221  2255260 if (node == null) {
222  2 throw new IllegalArgumentException(val + " does not exist in graph");
223    }
224  2255258 return node;
225    }
226   
 
227  3287 toggle @Override
228    public final void clearNodeAnnotations() {
229  3287 for (GraphNode<N, E> n : getNodes()) {
230  16377 n.setAnnotation(null);
231    }
232    }
233   
234    /** Makes each edge's annotation null. */
 
235  4 toggle public final void clearEdgeAnnotations() {
236  4 for (GraphEdge<N, E> e : getEdges()) {
237  4 e.setAnnotation(null);
238    }
239    }
240   
241    /**
242    * Pushes nodes' annotation values. Restored with
243    * {@link #popNodeAnnotations()}. Nodes' annotation values are cleared.
244    */
 
245  320 toggle public final void pushNodeAnnotations() {
246  320 if (nodeAnnotationStack == null) {
247  250 nodeAnnotationStack = Lists.newLinkedList();
248    }
249  320 pushAnnotations(nodeAnnotationStack, getNodes());
250    }
251   
252    /**
253    * Restores nodes' annotation values to state before last
254    * {@link #pushNodeAnnotations()}.
255    */
 
256  320 toggle public final void popNodeAnnotations() {
257  320 Preconditions.checkNotNull(nodeAnnotationStack,
258    "Popping node annotations without pushing.");
259  320 popAnnotations(nodeAnnotationStack);
260    }
261   
262    /**
263    * Pushes edges' annotation values. Restored with
264    * {@link #popEdgeAnnotations()}. Edges' annotation values are cleared.
265    */
 
266  320 toggle public final void pushEdgeAnnotations() {
267  320 if (edgeAnnotationStack == null) {
268  250 edgeAnnotationStack = Lists.newLinkedList();
269    }
270  320 pushAnnotations(edgeAnnotationStack, getEdges());
271    }
272   
273    /**
274    * Restores edges' annotation values to state before last
275    * {@link #pushEdgeAnnotations()}.
276    */
 
277  320 toggle public final void popEdgeAnnotations() {
278  320 Preconditions.checkNotNull(edgeAnnotationStack,
279    "Popping edge annotations without pushing.");
280  320 popAnnotations(edgeAnnotationStack);
281    }
282   
283    /**
284    * A generic edge.
285    *
286    * @param <N> Value type that the graph node stores.
287    * @param <E> Value type that the graph edge stores.
288    */
 
289    public interface GraphEdge<N, E> extends Annotatable {
290    /**
291    * Retrieves the edge's value.
292    *
293    * @return The value.
294    */
295    E getValue();
296   
297    GraphNode<N, E> getNodeA();
298   
299    GraphNode<N, E> getNodeB();
300    }
301   
302    /**
303    * A simple implementation of SubGraph that calculates adjacency by iterating
304    * over a node's neighbors.
305    */
 
306    class SimpleSubGraph<N, E> implements SubGraph<N, E> {
307    private Graph<N, E> graph;
308    private List<GraphNode<N, E>> nodes = Lists.newArrayList();
309   
 
310  1170 toggle SimpleSubGraph(Graph<N, E> graph) {
311  1170 this.graph = graph;
312    }
313   
 
314  51442 toggle @Override
315    public boolean isIndependentOf(N value) {
316  51442 GraphNode<N, E> node = graph.getNode(value);
317  51442 for (GraphNode<N, E> n : nodes) {
318  70210 if (graph.getNeighborNodes(n.getValue()).contains(node)) {
319  49795 return false;
320    }
321    }
322  1647 return true;
323    }
324   
 
325  1651 toggle @Override
326    public void addNode(N value) {
327  1651 nodes.add(graph.getNodeOrFail(value));
328    }
329    }
330   
331    /**
332    * Pushes a new list on stack and stores nodes annotations in the new list.
333    * Clears objects' annotations as well.
334    */
 
335  640 toggle private static void pushAnnotations(
336    Deque<GraphAnnotationState> stack,
337    Collection<? extends Annotatable> haveAnnotations) {
338  640 stack.push(new GraphAnnotationState(haveAnnotations.size()));
339  640 for (Annotatable h : haveAnnotations) {
340  4240 stack.peek().add(new AnnotationState(h, h.getAnnotation()));
341  4240 h.setAnnotation(null);
342    }
343    }
344   
345    /**
346    * Restores the node annotations on the top of stack and pops stack.
347    */
 
348  640 toggle private static void popAnnotations(Deque<GraphAnnotationState> stack) {
349  640 for (AnnotationState as : stack.pop()) {
350  4240 as.first.setAnnotation(as.second);
351    }
352    }
353    }
  • Report generated by OpenClover v 4.4.1 on Mon Jan 2 2023 15:17:08 MST using coverage data from Mon Jan 2 2023 15:16:37 MST.
  • OpenClover is free and open-source software.